﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

//最后一块石头的重量Ⅱ
class Solution
{
public:
    int lastStoneWeightII(vector<int>& stones)
    {
        // 任意两块⽯头在⼀起粉碎，重量相同的部分会被丢掉，重量有差异的部分会被留下来。那就相当于在原始的数据的前⾯，加上加号或者减号，是最终的结果最⼩即可
        // 在数组中选择⼀些数，让这些数的和尽量接近 sum / 2
        // dp[i][j] 表⽰在前 i 个元素中选择，总和不超过 j，此时所有元素的最⼤和
        int sum = 0;
        for (auto x : stones) sum += x;
        int aim = sum / 2;
        int n = stones.size();
        vector<vector<int>> dp(n + 1, vector<int>(aim + 1));
        // dp[i][j] = dp[i-1][j] 不选择i位置的数
        // dp[i][j] = dp[i-1][j-stones[i]] + stones[i] 选择i位置的数 j >= stones[i]
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= aim; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= stones[i - 1])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
            }
        }

        // 根据「状态表⽰」，先找到最接近 sum / 2 的最⼤和 dp[n][sum / 2] ；
        // 因为我们要的是两堆⽯⼦的差，因此返回 sum - 2 * dp[n][sum / 2] 。
        return sum - 2 * dp[n][aim];
    }
};

// 滚动数组优化
class Solution
{
public:
    int lastStoneWeightII(vector<int>& stones)
    {
        int sum = 0;
        for (auto x : stones) sum += x;
        int aim = sum / 2;
        int n = stones.size();
        vector<int> dp(aim + 1);
        for (int i = 1; i <= n; i++)
        {
            for (int j = aim; j >= stones[i - 1]; j--)
                dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
        }

        return sum - 2 * dp[aim];
    }
};


//【模板】完全背包
#include <iostream>
#include <string.h>

using namespace std;

const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];

int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // dp[i][j]:表示从前i个物品中体积不超过j的最大价值
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    }

    cout << dp[n][V] << endl;
    memset(dp, 0, sizeof dp);
    // dp[i][j]:表示从前i个物品中体积等于j的最大价值
    // 第一行后面的结果不存在，置为-1,或者置为最小值的一半-0x3f3f3f3f
    for (int j = 1; j <= V; j++) dp[0][j] = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    }

    cout << (dp[n][V] < 0 ? 0 : dp[n][V]) << endl;

    return 0;
}

//滚动数组优化  
//dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]);
// 依赖当前行左边的值,所以需要从左往右进行遍历
int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    cout << dp[V] << endl;
    memset(dp, 0, sizeof dp);
    for (int j = 1; j <= V; j++) dp[j] = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    cout << (dp[V] < 0 ? 0 : dp[V]) << endl;

    return 0;
}
//零钱兑换
class Solution
{
public:
    int coinChange(vector<int>& coins, int amount)
    {
        const int INF = 0x3f3f3f3f;
        // dp[i][j]:表示从前i个硬币中挑选综合等于j的最少硬币数
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        // 第一行从第二个后面的都是无效的数据置为-1或者最大值的一半
        for (int j = 1; j <= amount; j++) dp[0][j] = INF;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1])
                    dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        }

        return dp[n][amount] >= INF ? -1 : dp[n][amount];
    }
};

// 滚动数组进行优化
class Solution
{
public:
    int coinChange(vector<int>& coins, int amount)
    {
        const int INF = 0x3f3f3f3f;
        int n = coins.size();
        vector<int> dp(amount + 1);
        // 第一行从第二个后面的都是无效的数据置为-1或者最大值的一半
        for (int j = 1; j <= amount; j++) dp[j] = INF;
        for (int i = 1; i <= n; i++)
            for (int j = coins[i - 1]; j <= amount; j++)
                dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
        return dp[amount] >= INF ? -1 : dp[amount];
    }
};
int main()
{
	return 0;
}